/**
 * 10. 正则表达式匹配
 * https://leetcode-cn.com/problems/regular-expression-matching/
 */

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
function isMatch(s, p) {
  const dp = new Array(s.length + 1);
  for (let i = 0; i <= s.length; i += 1) {
    dp[i] = new Array(p.length + 1).fill(false);
  }
  dp[0][0] = true;
  for (let j = 2; j <= p.length; j += 1) {
    if (p.charAt(j - 1) === '*') {
      dp[0][j] = dp[0][j - 2];
    }
  }
  for (let i = 1; i <= s.length; i += 1) {
    const charS = s.charAt(i - 1);
    for (let j = 1; j <= p.length; j += 1) {
      // console.log(`match\n  ${s.substr(0, i)}\n  ${p.substr(0, j)}`);
      const charP = p.charAt(j - 1);
      if (charS === charP || charP === '.') {
        dp[i][j] = dp[i - 1][j - 1];
      } else if (charP === '*') {
        if (dp[i][j - 1]) {
          dp[i][j] = true;
        } else {
          const charPPre = p.charAt(j - 2);
          if (charS === charPPre || charPPre === '.') {
            dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
          } else {
            dp[i][j] = dp[i][j - 2];
          }
        }
      }
      // console.log(`match result ${dp[i][j]}`);
    }
  }
  return dp[s.length][p.length];
}

console.log(isMatch('aa', 'a') === false);
console.log(isMatch('aa', 'a*') === true);
console.log(isMatch('ab', '.*') === true);
console.log(isMatch('a', 'a.*') === true);
console.log(isMatch('aasdfasdfasdfasdfas', 'aasdf.*asdf.*asdf.*asdf.*s') === true);
